In this section, a valid-time model, able to handle imperfect valid-time notions, will be presented. First, the representation and storage of valid-time will be presented. Next, an approach to query the model is proposed. Finally, an example is given.

\subsection{Valid-time Intervals}
\subsubsection{Representation}
\label{subsec:representation-ill-known}
A database models real objects by storing the values of an object for each attribute describing a property of the object. Thus, a valid-time database following the presented proposal will model the time during which an object in a certain state is valid, by associating a \emph{Possibilistic Valid-time Period} (PVP) to the record describing this object state:

\begin{definition}
A \emph{Possibilistic Valid-time Period} is an ill-known interval in time, which models a time period during which an object in a certain state is valid.
\end{definition}

Because a PVP is an ill-known interval, it allows modelling the uncertainty about the start and/or end point of a time interval (and thus about the time interval itself) if such uncertainty exists. The interpretation is \emph{disjunctive}: the PVP represents exactly one valid-time interval, but precisely \emph{which} interval is represented, is (partially) unknown. In the presented model, only PVPs are considered of which the possibility distributions of the possibilistic variables defining the start and end point of the ill-known interval have exactly the same characteristics as the membership functions of fuzzy numbers. A perfectly known start or end point can then be modelled by such an ill-known value defined by a possibilistic variable $P$ for which $\exists ! x : \mu_{P}(x) > 0$.

As mentioned in \cite{Pons2011}, this approach differs from the one where a valid-time period is represented by one fuzzy set. Such a fuzzy set is seen as a possibility distribution on $\mathbb{R}$ and thus defines just one ill-known value. However, in the presented approach, a time period is modelled using an ill-known set, which is defined by a possibility distribution on $\Pow(\mathbb{R})$.

\subsubsection{Storage}
\label{subsec:storage}
To store a PVP, the possibility distributions defining the ill-known start and end point are stored. To store such a possibility distribution, the representation as used in the fuzzy interface for relational databases \emph{FIRST}~\cite{Medina1994}, \cite{Galindo1998} is used. Using this representation, it is possible to represent not only fuzzy numbers, but also (fuzzy) constants. To store an ill-known value, four values (FT, F1, F2 and F3) are stored. They are explained in Table \ref{table:relational-representation-pvp}. Note that while NULL denotes the fuzzy constant NULL, N denotes a null value in the database \cite{Medina1994}.


\vspace{-10pt}

\begin{table}
\centering
\caption{Relational representation for an ill-known time point. FT denotes Fuzzy Type. Field FT indicates that the values stored in F1, F2 and F3 denote either NULL, UNKNOWN, UNDEFINED or a triangular possibility distribution $M$ = $\left[D,\ a,\ b \right]$. Fields F1, F2 and F3 contain the actual values.}

\begin{tabular}{c c c c c c l p{2cm}}
\hline
Value & FT & F1 & F2 & F3 & $\mu(x)$ & Description \\ \hline
UNKNOWN & 0 & N & N & N  & $1$ & Any value is equally possible\\ 
UNDEFINED & 1 & N & N & N & $0$ & The value is not defined \\
NULL & 2 & N & N & N &not defined & Nothing is known about the value \\ 
$M$ & 3 & $D$ & $a$ & $b$ & $\mu_{M}$ & Ill-known value \\ 
\hline 
\end{tabular}
\label{table:relational-representation-pvp}

\vspace{10pt}


\end{table}

\vspace{-25pt}

\subsection{Querying Ill-known Valid-time Intervals}
This subsection discusses a tool for querying. The focus will evidently lie on the querying of valid-time periods. First, the query structure will be defined, followed by the evaluation and ranking methods.

\subsubsection{Query Structure}
It is important to notice that every valid-time notion in the database is represented using a PVP. In the presented framework, a query has two separate parts:

\begin{definition}
A query $\tilde Q$ is specified by:
\begin{equation}
\label{eq:query-definition}
\tilde Q = \left( Q^{time}, Q \right)
\end{equation}
\end{definition}
Here, $Q$ denotes the collection of (possibly fuzzy) non-temporal preferences of the user and $Q^{time}$ denotes the temporal constraint given by the user:
\begin{definition}
 $Q^{time}$ is defined by:
\begin{equation}
Q^{time} = \left( I , AR \right)
\end{equation}
\end{definition}
Here, $I$ is a crisp time interval and $AR$ is one of Allen's relations \cite{Allen1983}. The interpretation is that for a record with valid-time period given by a PVP $J$, the user requires that $I$ $AR$ $J$ holds.


\subsubsection{Query Evaluation}
In fuzzy querying of regular (relational) databases, the modelling of query satisfaction is a matter of degree. Usually, the evaluation of the query requirements for a record results in a satisfaction degree $s$, where $s$ lies in $\left[0,1\right]$, where 0 denotes total dissatisfaction and 1 denotes complete satisfaction. In crisp querying, the evaluation of query requirements for a record results in the accepting or rejecting of the record as a part of the result set. This can be modelled using satisfaction degrees, by assigning rejection a degree of $0$ and acceptance a degree of $1$ and not using any other value in $\left[0,1\right]$.

The evaluation of a query $\tilde{Q} = \left( Q^{time}, Q \right)$, where $Q^{time} = \left( I, AR \right)$ is now handled as follows. For each record $r$ in the database, with the valid-time notion of $r$ being specified by a PVP $J$, two things happen independently:


\begin{itemize}
\item
The preferences expressed in $Q$ are evaluated, resulting in a satisfaction degree denoted here $e_{Q}(r)$. The presented model accepts any sound way of calculating this evaluation, as long as $e_{Q}(r) \in \left[0,1\right]$. 
\item
Depending on AR, a specific set of ill-known constraints is considered, which can be found in Table 2. The possibility and necessity that $r$ fulfills all these constraints are calculated using formulas based on equations \eqref{ill-known-pos} respectively \eqref{ill-known-nec} and aggregated using the $\min$ operator. 
\end{itemize}


\begin{table}[h]
\label{tab:allen-relations}
\caption{Allen's relations used in the framework. Here, $I = \left[a, b\right]$ denotes the PVP in the query, $J = \left[X, Y\right]$ denotes the PVP of the record, with $\pi_{X}$ and $\pi_{Y}$ the possibility distributions of $X$ and $Y$ respectively. For each of Allen's relations $AR$, the corresponding value in column `Constraints' gives the constraints corresponding to $AR$. The last column contains the corresponding formula to calculate the possibility that $I$ satisfies all constraints given in column `Constraints', which are based on equation \eqref{ill-known-pos}.}

\centering
\begin{tabular}{|c|l|l|}
\hline
\multirow{2}{*}
{Allen Relation}  & {Constraints} & $\Pos($ I satisfies all constraints  \\
 & & $C_{i}, i = 1,2,\ldots)$ \\
\hline
I before J & $C_1 \triangleq \left(<,X\right)$ & $\sup_{a>w}\pi_x(w)$\\
\hline

\multirow{2}{*}
{I equal J} & $C_1\triangleq \left(\geq,X\right)$,$C_2\triangleq \left(\neq,X\right)$ & $\min ( \sup_{a \leq w}\pi_x(w),\pi_x(w),$ \\
 & $C_3\triangleq \left(\leq,Y\right)$,$C_4\triangleq \left(\neq,Y\right)$ & $\sup_{b \geq w}\pi_Y(w),\pi_Y(w))$\\
\hline

I meets J & $C_1\triangleq \left(\leq,X\right)$ ,$C_2\triangleq \left(\neq,X\right)$ & $\min (\sup_{a\geq w} \pi_X(w),$ $\pi_X(w))$ \\
\hline

\multirow{2}{*}
{I overlaps J} & $C_1\triangleq \left(<,Y\right)$,$C_2\triangleq \left(\leq,X\right)$ & $\min ( \sup_{b>w}\pi_Y(w), $ \\
 & $C_3\triangleq \left(\geq,X\right)$ & $\sup_{a \geq w}\pi_X(w),\sup_{a \leq w}\pi_X(w))$ \\
\hline

\multirow{2}{*}
{I during J} & $C_1\triangleq \left(>,X\right)$, $C_2\triangleq \left(\leq,Y\right)$ & $\max ( \min ( \sup_{a<w}\pi_X(w),\sup_{b \geq w}\pi_Y(w)),$ \\
 & $C_3\triangleq \left(\geq,X\right)$ ,$C_4\triangleq \left(<,Y\right)$ & $\min ( \sup_{a \leq w }\pi_X(w),\sup_{b>w}\pi_Y(w)$\\
\hline

{I starts J} & $C_1\triangleq \left(\geq,X\right)$,$C_2\triangleq \left(\neq,X\right)$  & $\min( \sup_{a \leq w}\pi_X(w),$ $\pi_X(w))$\\
\hline

{I finishes J} & $C_1\triangleq \left(\leq,Y\right)$, $C_2\triangleq \left(\neq,Y\right)$  & $\min ( \sup_{b \geq w} \pi_Y(w),$ $\pi_Y(w))$ \\
\hline 

\end{tabular}

\vspace{10pt}


\vspace{-25pt}

\end{table}


\vspace{-5pt}

\subsubsection{Ranking and Aggregation}
In order to present the results to the user, a crude ranking method is used: for every record $r$, the sum of $\Pos_{Q^{time}}(r)$ and $\Nec_{Q^{time}}(r)$ gives an evaluation score $e'_{Q^{time}}(r)$ in interval $\left[0,2\right]$. Because necessity cannot exceed $0$ unless possibility is $1$, this gives a natural ranking score. Some authors ~\cite{Bosc2010a} mentioned before that the possibility and necessity measures result in a total order in the set of events.  This $e'_{Q^{time}}(r)$ is then rescaled to the unit interval, resulting in $e_{Q^{time}}(r)$. The final ranking $e_{final}(r)$ is now given by a convex combination:


\begin{equation}
\label{eq:convex-comb}
e_{final}(r)\ =\ \omega*e_{Q}(r)\ +\ (1-\omega)*e_{Q^{time}}(r), \omega \in \left[0, 1 \right]
\end{equation}

The use of this convex combination allows a record to make up for a low score for the temporal constraint by a good score for the non-temporal constraint (or vice versa). Changing $\omega$ also allows granting the temporal constraint more weight with respect to the non-temporal constraint (or vice versa).

\begin{example} 
Consider the example relation given in Table \ref{tb:car-models} describing car models, containing general attributes (model name, manufacturer, car segment) and one temporal attribute (stored as explained in subsection \ref{subsec:storage}) describing the approximate period of time during which the car model was sold. The value for $D$ is stored in \emph{yyyy} format and $a$ and $b$ are represented by an integer. The ID field identifies a car model while the field Instance ID (IID) identifies the instance for a car model, thus a car model in a certain state.
\end{example}


\begin{table}[h]
\centering
\caption{Example database}
\begin{tabular}{c c c c c c c}
\hline
ID & IID & Segment & Manufacturer & Name & Start & End  \\ [0.5ex]
\hline
001 & 1 & B & Peugeot & 205 & [1985,2,3] & [1997,2,1] \\
002 & 1 & C & Peugeot & 305 & [1977,2,2] & [1989,2,3] \\
003 & 1 & B & Citroen & C2 & [2002,2,2] & [2006,1,1] \\
001 & 2 & B & Peugeot & 206 & [2000,1,2] & [2011,2,1] \\
001 & 3 & B & Peugeot & 207 & [2006,1,1] & [2011,1,1]\\
\hline
\end{tabular}
\vspace{10pt}
\label{tb:car-models}
\vspace{-30pt}
\end{table}

Consider the following query:
\begin{center}
\emph{The user wants to obtain a list of models from segment B, made by manufacturer Peugeot before the year interval 2001-2005}\\
\end{center}

Using the introduced notations in \eqref{eq:query-definition}, the query is translated to: 

\begin{align}
Q^{time} & = \left(\left[ 2001, 2005 \right], before\right) \\
Q & = \left(Segment =  B\right) \wedge \left(Manufacturer = Peugeot\right)
\end{align}


\begin{table}[ht]
\caption{Result table and ranking}
\centering
\begin{tabular}{c c c c c c c}
\hline
ID & IID &  $\Pos_{Q^{time}}$ & $\Nec_{Q^{time}}$ & $e_{Q^{time}} (rescaled)$ & $Q$ & $e_{final}$ ($\omega=0.5$) \\ [0.5ex]
\hline
001 & 1 & 1 &  1 & 1 & 1 & 1 \\
002 & 1 & 1 & 1 & 1 & 0.5 & 0.75 \\
003 & 1 & 1 & 0.5 & 0.75 &0 & 0.375\\
001 & 2 & 1 & 0 & 0.5 &1 & 0.75 \\
001 & 3 & 0 & 0 & 0 &1 & 0.5\\
\hline
\end{tabular}
\label{tb:results}
\end{table}

Table \ref{tb:results} shows a natural and gradual ranking for the results. The last record, (ID 001, IID 3) shows also that with $\omega$ = 0.5 both temporal and regular criteria have the same importance.